11448 - Who said crisis/11448.cpp

   1 /**
   2  * Big integer class, optimized for decimal integers.
   3  * Stores and manipulates integers represented as byte arrays,
   4  * where each byte is a decimal digit. If you're looking for
   5  * robust, bug-free, efficient code, keep looking. This is a quick
   6  * and dirty hack. Some day I'll write a templatized BigInt, where
   7  * you will be able to select the base in which to store the
   8  * number. When that day comes, most of this code will be thrown
   9  * away.
  10  *
  11  * BUGS:
  12  *      operator-(int) does not work.
  13  *
  14  *      BigInt doesn't play nice with long long. Either use int
  15  *      or string.
  16  *
  17  * INVARIANTS:
  18  *      - capacity is never smaller than 16
  19  *      - capacity is not the smallest it can be because every
  20  *         modifying member function first grows digits as much as
  21  *         it might ever need and then does its job.
  22  * FIELD TESTING:
  23  *      - Passed numerous problems on Valladolid, including
  24  *          107, 288, 324, 424, 465, 485, 495, 560, 619, 623, etc.
  25  *
  26  * COMPATIBILITY:
  27  *      - This class was written for the g++ compiler and uses some
  28  *          of the g++ extensions (like "long double" and the ">?="
  29  *          operator). If you want to compile this under Micro$oft's
  30  *          "compiler", I don't want to talk to you.
  31  *
  32  * LAST MODIFIED: October 5, 2005
  33  *
  34  * This file is part of my library of algorithms found here:
  35  *      http://www.palmcommander.com:8081/tools/
  36  * LICENSE:
  37  *      http://www.palmcommander.com:8081/tools/LICENSE.html
  38  * Copyright (c) 2002-2004
  39  * Contact author:
  40  *      igor at cs.ubc.ca
  41  **/
  42
  43 #include <stdio.h>
  44 #include <string.h>
  45 #include <string>
  46 #include <iostream>
  47 #include <sstream>
  48 #include <math.h>
  49
  50 using namespace std;
  51
  52 #ifndef min
  53 #define min(x,y) ((x) < (y) ? (x) : (y))
  54 #endif
  55
  56 #ifndef max
  57 #define max(x,y) ((x) > (y) ? (x) : (y))
  58 #endif
  59
  60 class BigInt
  61 {
  62     private:
  63         char *digits;
  64         int size;            // number of used bytes (digits)
  65         int capacity;        // size of digits
  66         int sign;            // -1, 0 or +1
  67
  68     public:
  69         /** Creates a BigInt with initial value n and initial capacity cap **/
  70         BigInt( int n, int cap );
  71
  72         /** Creates a BigInt with initial value n **/
  73         BigInt( int n );
  74
  75         /** Creates a BigInt with initial value floor( d ) **/
  76         BigInt( long double d );
  77
  78         /** Creates a BigInt with value 0 **/
  79         BigInt();
  80
  81         /** Creates a BigInt by reading the value from a string **/
  82         BigInt( string s );
  83
  84         /** Creates a BigInt by reading the value from a C string **/
  85         BigInt( const char s[] );
  86
  87         /** Copy constructor **/
  88         BigInt( const BigInt &n );
  89
  90         /** Assignment operators **/
  91         const BigInt &operator=( const BigInt &n );
  92         const BigInt &operator=( int n );
  93
  94         /** Cleans up **/
  95         ~BigInt();
  96
  97         /** Removes any leading zeros and adjusts the sign **/
  98         void normalize();
  99
 100         /** Returns the sign of n: -1, 0 or 1 **/
 101         static int sig( int n );
 102
 103         /** Returns the sign of n: -1, 0 or 1 **/
 104         static int sig( long double n );
 105
 106         /** Returns the number of decimal digits **/
 107         inline int length() { return size; }
 108
 109         /** Arithmetic **/
 110         BigInt operator++();
 111         BigInt operator++( int );
 112         BigInt operator--();
 113         BigInt operator--( int );
 114         BigInt operator-();
 115         BigInt operator+ ( int n    );
 116         BigInt operator+ ( BigInt n );
 117         BigInt&operator+=( int n    );
 118         BigInt&operator+=( BigInt n );
 119         BigInt operator- ( int n    );
 120         BigInt operator- ( BigInt n );
 121         BigInt&operator-=( int n    );
 122         BigInt&operator-=( BigInt n );
 123         BigInt operator* ( int n    );
 124         BigInt operator* ( BigInt n );
 125         void   operator*=( int n    );
 126         void   operator*=( BigInt n );
 127         BigInt operator/ ( int n    );
 128         BigInt operator/ ( BigInt n );
 129         void   operator/=( int n    );
 130         void   operator/=( BigInt n );
 131         int    operator% ( int n    );
 132         BigInt operator% ( BigInt n );
 133         void   operator%=( int n    );
 134         void   operator%=( BigInt n );
 135         int divide( int n );              // Divides storing quotient in *this and returning the remainder
 136         BigInt divide( BigInt n );        // Divides storing quotient in *this and returning the remainder
 137         BigInt operator* ( long double n ); // Multiplies by a double and truncates (always under-estimates!)
 138         void   operator*=( long double n ); // Multiplies by a double and truncates (always under-estimates!)
 139
 140         /** Bitwise arithmetic **/
 141         BigInt operator<< ( int n    );
 142         void   operator<<=( int n    );
 143         BigInt operator>> ( int n    );   // Works differently for negative numbers
 144         void   operator>>=( int n    );   // Works differently for negative numbers
 145 /*
 146         BigInt operator&  ( int n    );
 147         BigInt operator&  ( BigInt n );
 148         void   operator&= ( int n    );
 149         void   operator&= ( BigInt n );
 150         BigInt operator|  ( int n    );
 151         BigInt operator|  ( BigInt n );
 152         void   operator|= ( int n    );
 153         void   operator|= ( BigInt n );
 154         BigInt operator^  ( int n    );
 155         BigInt operator^  ( BigInt n );
 156         void   operator^= ( int n    );
 157         void   operator^= ( BigInt n );
 158         BigInt operator~();
 159 */
 160         /** Concatenation ;-) **/
 161         BigInt operator,( int n );
 162         BigInt operator,( BigInt n );
 163
 164         /** Casting **/
 165         bool operator!();
 166         operator bool();
 167         //operator int();   //XXX: Don't do this!!! It takes precedence over operator+(int,BigInt)
 168         operator string();
 169
 170         /** Comparison **/
 171         bool operator<( BigInt n );
 172         bool operator>( BigInt n );
 173         bool operator==( BigInt n );
 174         bool operator<=( BigInt n );
 175         bool operator>=( BigInt n );
 176         bool operator<( int n );
 177         bool operator>( int n );
 178         bool operator==( int n );
 179         bool operator<=( int n );
 180         bool operator>=( int n );
 181         int compare( BigInt n );
 182
 183         /** Returns the lowest value as an integer (watch out for overflow) **/
 184         int toInt();
 185
 186         /** Returns the value as a decimal string **/
 187         string toString();
 188
 189         /** Outputs decimal value to stdout **/
 190         void print();
 191
 192         /** Outputs the decimal value, with commas **/
 193         void printWithCommas( ostream &out );
 194
 195     private:
 196         /** Expansion **/
 197         void grow();
 198
 199     /** I/O Friends **/
 200     friend istream &operator>>( istream &in, BigInt &n );
 201     friend ostream &operator<<( ostream &out, BigInt n );
 202
 203     /** Logarithms **/
 204     friend long double log2( BigInt x, long double epsilon );
 205     inline friend long double log( BigInt x, long double epsilon );
 206     inline friend long double log10( BigInt x, long double epsilon );
 207     inline friend long double lg( BigInt x, long double epsilon );
 208     inline friend long double ln( BigInt x, long double epsilon );
 209 };
 210
 211 BigInt operator+( int m, BigInt &n )
 212 {
 213     return n + m;
 214 }
 215
 216 BigInt operator-( int m, BigInt &n )
 217 {
 218     return -n + m;
 219 }
 220
 221 BigInt operator*( int m, BigInt &n )
 222 {
 223     return n * m;
 224 }
 225
 226 BigInt operator/( int m, BigInt &n )
 227 {
 228     return BigInt( m ) / n;
 229 }
 230
 231 BigInt operator%( int m, BigInt &n )
 232 {
 233     return BigInt( m ) % n;
 234 }
 235
 236 /** Misc **/
 237 inline bool isDigit( int c )
 238 {
 239     return( c >= ( int )'0' && c <= ( int )'9' );
 240 }
 241
 242 /** Input/Output **/
 243 istream &operator>>( istream &in, BigInt &n )           // FIXME: see inside
 244 {
 245     n.size = 0;
 246     n.sign = 1;
 247     int sign = 1;
 248     int c;
 249     while( ( c = in.peek() ) >= 0 &&
 250            ( c == ' ' || c == '\t' || c == '\r' || c == '\n' ) )
 251         in.get();
 252     if( c < 0 || ( c != ( int )'-' && !isDigit( c ) ) )
 253     {
 254         in >> c;                // XXX: force in.fail()
 255         return in;
 256     }
 257     if( c == ( int )'-' ) { sign = -1; in.get(); }
 258
 259     // FIXME: Extremely inefficient! Use a string.
 260     while( ( c = in.peek() ) >= 0 && isDigit( c ) )
 261     {
 262         in.get();
 263         n *= 10;
 264         n += ( c - ( int )'0' );
 265     }
 266     n.sign = sign;      //XXX: assign n.sign directly after fixing the FIXME
 267     n.normalize();
 268     return in;
 269 }
 270
 271 ostream &operator<<( ostream &out, BigInt n )       //FIXME: make more efficient
 272 {
 273     return out << n.toString();
 274 }
 275
 276 BigInt::BigInt( int n, int cap )
 277 {
 278     cap = max( cap, ( int )sizeof( n ) * 8 );
 279     capacity = cap;
 280     sign = sig( n );
 281     n *= sign;
 282     digits = new char[cap];
 283     memset( digits, 0, cap );
 284     for( size = 0; n; size++ )
 285     {
 286         digits[size] = n % 10;
 287         n /= 10;
 288     }
 289 }
 290
 291 BigInt::BigInt( int n )
 292 {
 293     capacity = 1024;
 294     sign = sig( n );
 295     n *= sign;
 296     digits = new char[capacity];
 297     memset( digits, 0, capacity );
 298     size = 0;
 299     while( n )
 300     {
 301         digits[size++] = n % 10;
 302         n /= 10;
 303     }
 304 }
 305
 306 BigInt::BigInt( long double d )
 307 {
 308     capacity = 1024;
 309     sign = ( d < 0 ? -1 : d > 0 ? 1 : 0 );
 310     d *= sign;
 311     digits = new char[capacity];
 312     memset( digits, 0, capacity );
 313     size = 0;
 314     d = floor( d );
 315     while( d > 0 )
 316     {
 317         digits[size++] = 0 >? ( int )( ( d - floor( d / 10 ) * 10 ) + 0.5 ) <? 9;
 318         d = floor( d / 10 );
 319     }
 320 }
 321
 322 BigInt::BigInt()
 323 {
 324     capacity = 128;
 325     sign = 0;
 326     digits = new char[capacity];
 327     memset( digits, 0, capacity );
 328     size = 0;
 329 }
 330
 331 BigInt::BigInt( string s )
 332 {
 333     capacity = max( ( int )s.size(), 16 );
 334     sign = 0;
 335     digits = new char[capacity];
 336     memset( digits, 0, capacity );
 337
 338     istringstream in( s );
 339     in >> ( *this );
 340 }
 341
 342 BigInt::BigInt( const char s[] )
 343 {
 344     capacity = max( ( int )strlen( s ), 16 );
 345     sign = 0;
 346     digits = new char[capacity];
 347     memset( digits, 0, capacity );
 348
 349     istringstream in( s );
 350     in >> ( *this );
 351 }
 352
 353 BigInt::BigInt( const BigInt &n )
 354 {
 355     capacity = n.capacity;
 356     sign = n.sign;
 357     size = n.size;
 358     digits = new char[capacity];
 359     memcpy( digits, n.digits, capacity );
 360 }
 361
 362 const BigInt &BigInt::operator=( const BigInt &n )
 363 {
 364     if( &n != this )
 365     {
 366         if( capacity < n.size )
 367         {
 368             capacity = n.capacity;
 369             delete [] digits;
 370             digits = new char[capacity];
 371         }
 372         sign = n.sign;
 373         size = n.size;
 374         memcpy( digits, n.digits, size );
 375         memset( digits + size, 0, capacity - size );
 376     }
 377     return *this;
 378 }
 379
 380 const BigInt &BigInt::operator=( int n )
 381 {
 382     sign = sig( n );
 383     n *= sign;
 384     for( size = 0; n; size++ )
 385     {
 386         digits[size] = n % 10;
 387         n /= 10;
 388     }
 389     return *this;
 390 }
 391
 392 BigInt::~BigInt()
 393 {
 394     delete [] digits;
 395 }
 396
 397 void BigInt::normalize()
 398 {
 399     while( size && !digits[size-1] ) size--;
 400     if( !size ) sign = 0;
 401 }
 402
 403 int BigInt::sig( int n )
 404 {
 405     return( n > 0 ? 1 : ( n == 0 ? 0 : -1 ) );
 406 }
 407
 408 int BigInt::sig( long double n )
 409 {
 410     return( n > 0 ? 1 : ( n == 0 ? 0 : -1 ) );
 411 }
 412
 413 int BigInt::toInt()
 414 {
 415     int result = 0;
 416     for( int i = size - 1; i >= 0; i-- )
 417     {
 418         result *= 10;
 419         result += digits[i];
 420         if( result < 0 ) return sign * 0x7FFFFFFF;
 421     }
 422     return sign * result;
 423 }
 424
 425 string BigInt::toString()
 426 {
 427     string s = ( sign >= 0 ? "" : "-" );
 428     for( int i = size - 1; i >= 0; i-- )
 429         s += ( digits[i] + '0' );
 430     if( size == 0 ) s += '0';
 431     return s;
 432 }
 433
 434 void BigInt::print()        //FIXME: make more efficient
 435 {
 436     cout << toString();
 437 }
 438
 439 void BigInt::printWithCommas( ostream &out )
 440 {
 441     if( sign < 0 ) out.put( '-' );
 442     for( int i = size - 1; i >= 0; i-- )
 443     {
 444         out.put( digits[i] + '0' );
 445         if( !( i % 3 ) && i ) out.put( ',' );
 446     }
 447     if( size == 0 ) out.put( '0' );
 448 }
 449
 450 void BigInt::grow()
 451 {
 452     char *olddigits = digits;
 453     int oldCap = capacity;
 454     capacity *= 2;
 455     digits = new char[capacity];
 456     memcpy( digits, olddigits, oldCap );
 457     memset( digits + oldCap, 0, oldCap );
 458     delete [] olddigits;
 459 }
 460
 461 BigInt BigInt::operator++()
 462 {
 463     operator+=( 1 );
 464     return *this;
 465 }
 466
 467 BigInt BigInt::operator++( int )
 468 {
 469     return operator++();
 470 }
 471
 472 BigInt BigInt::operator--()
 473 {
 474     operator-=( 1 );
 475     return *this;
 476 }
 477
 478 BigInt BigInt::operator--( int )
 479 {
 480     return operator--();
 481 }
 482
 483 BigInt BigInt::operator-()
 484 {
 485     BigInt result( *this );
 486     result.sign *= -1;
 487     return result;
 488 }
 489
 490 BigInt BigInt::operator+( int n )
 491 {
 492     BigInt result( *this );
 493     result += n;
 494     return result;
 495 }
 496
 497 BigInt BigInt::operator+( BigInt n )
 498 {
 499     BigInt result( *this );
 500     result += n;
 501     return result;
 502 }
 503
 504 BigInt &BigInt::operator+=( int n )
 505 {
 506     if( size == capacity ) grow();
 507
 508     int nsign = sig( n );
 509     if( !nsign ) return *this;
 510     if( !sign ) sign = nsign;
 511     if( sign == nsign )
 512     {
 513         n *= nsign;
 514         int carry = 0;
 515         int i;
 516         for( i = 0; n || carry; i++ )
 517         {
 518             int dig = n % 10;
 519             int newdig = digits[i] + dig + carry;
 520             digits[i] = newdig % 10;
 521             carry = newdig / 10;
 522             n /= 10;
 523         }
 524         size = max( i, size );
 525     }
 526     else operator-=( -n );
 527     return *this;
 528 }
 529
 530 BigInt &BigInt::operator+=( BigInt n )
 531 {
 532     int maxS = max( size, n.size ) + 1;
 533     while( maxS >= capacity ) grow();        //FIXME: this is stupid
 534
 535     if( !n.sign ) return *this;
 536     if( !sign ) sign = n.sign;
 537     if( sign == n.sign )
 538     {
 539         int carry = 0;
 540         int i;
 541         for( i = 0; i < maxS - 1 || carry; i++ )
 542         {
 543             int newdig = carry;
 544             if( i < size ) newdig += digits[i];
 545             if( i < n.size ) newdig += n.digits[i];
 546             digits[i] = newdig % 10;
 547             carry = newdig / 10;
 548         }
 549         size = max( i, size );
 550     }
 551     else
 552     {
 553         n.sign *= -1;
 554         operator-=( n );
 555         n.sign *= -1;
 556     }
 557     return *this;
 558 }
 559
 560 BigInt BigInt::operator-( int n )
 561 {
 562     BigInt result( *this );
 563     result -= n;
 564     return result;
 565 }
 566
 567 BigInt BigInt::operator-( BigInt n )
 568 {
 569     BigInt result( *this );
 570     result -= n;
 571     return result;
 572 }
 573
 574 BigInt &BigInt::operator-=( int n )
 575 {
 576     if( size == capacity ) grow();
 577
 578     int nsign = sig( n );
 579     if( !nsign ) return *this;
 580     if( !sign ) sign = 1;
 581     if( sign == nsign )
 582     {
 583         BigInt bin = n;
 584         if( sign >= 0 && *this < bin || sign < 0 && *this > bin )
 585         {
 586             // Subtracting a bigger number
 587             operator=( toInt() - n );
 588             return *this;
 589         }
 590
 591         n *= nsign;
 592         int carry = 0;
 593         int i;
 594         for( i = 0; n || carry; i++ )
 595         {
 596             int dig = n % 10;
 597             int newdig = digits[i] - dig + carry;
 598             if( newdig < 0 ) newdig += 10, carry = -1;
 599             else carry = 0;
 600             digits[i] = newdig;
 601             n /= 10;
 602         }
 603         normalize();
 604     }
 605     else operator+=( -n );
 606     return *this;
 607 }
 608
 609 BigInt &BigInt::operator-=( BigInt n )
 610 {
 611     int maxS = max( size, n.size ) + 1;
 612     while( maxS >= capacity ) grow();        //FIXME: this is stupid
 613
 614     if( !n.sign ) return *this;
 615     if( !sign ) sign = 1;
 616     if( sign == n.sign )
 617     {
 618         if( sign >= 0 && *this < n || sign < 0 && *this > n )
 619         {
 620             // Subtracting a bigger number
 621             BigInt tmp = n;
 622             tmp -= *this;
 623             *this = tmp;
 624             sign = -sign;
 625             return *this;
 626         }
 627
 628         int carry = 0;
 629         int i;
 630         for( i = 0; i < maxS - 1; i++ )
 631         {
 632             int newdig = carry;
 633             if( i < size ) newdig += digits[i];
 634             if( i < n.size ) newdig -= n.digits[i];
 635             if( newdig < 0 ) newdig += 10, carry = -1;
 636             else carry = 0;
 637             digits[i] = newdig;
 638         }
 639         if( carry )     // Subtracted a bigger number, need to flip sign
 640         {
 641             if( i ) digits[0] = 10 - digits[0];
 642             size = ( i ? 1 : 0 );
 643             for( int j = 1; j < i; j++ )
 644             {
 645                 digits[j] = 9 - digits[j];
 646                 if( digits[i] ) size = j + 1;
 647             }
 648             sign *= -1;
 649         }
 650         normalize();
 651     }
 652     else
 653     {
 654         n.sign *= -1;
 655         operator+=( n );
 656         n.sign *= -1;
 657     }
 658     return *this;
 659 }
 660
 661 BigInt BigInt::operator*( int n )
 662 {
 663     BigInt result( 0, size + ( int )sizeof( n ) * 8 );
 664     int nsign = sig( n );
 665     n *= nsign;
 666     result.sign = sign * nsign;
 667     if( !result.sign ) return result;
 668
 669     int i, j;
 670     for( i = 0; n; i++ )
 671     {
 672         int dig = n % 10;
 673         if( dig )
 674         {
 675             int carry = 0;
 676             for( j = 0; j < size || carry; j++ )
 677             {
 678                 int newDig = result.digits[i + j] + ( j < size ? dig * digits[j] : 0 ) + carry;
 679                 result.digits[i + j] = newDig % 10;
 680                 carry = newDig / 10;
 681             }
 682         }
 683         n /= 10;
 684     }
 685     result.size = i + j - 1;
 686     return result;
 687 }
 688
 689 BigInt BigInt::operator*( BigInt n )
 690 {
 691     BigInt result( 0, size + n.size );
 692
 693     result.sign = sign * n.sign;
 694     if( !result.sign ) return result;
 695
 696     int i, j;
 697     for( i = 0; i < n.size; i++ )
 698     {
 699         if( n.digits[i] )
 700         {
 701             int carry = 0;
 702             for( j = 0; j < size || carry; j++ )
 703             {
 704                 int newDig =
 705                     result.digits[i + j] +
 706                     ( j < size ? n.digits[i] * digits[j] : 0 ) +
 707                     carry;
 708                 result.digits[i + j] = newDig % 10;
 709                 carry = newDig / 10;
 710             }
 711         }
 712     }
 713     result.size = i + j - 1;
 714
 715     return result;
 716 }
 717
 718 void BigInt::operator*=( int n )
 719 {
 720     operator=( operator*( n ) );
 721 }
 722
 723 void BigInt::operator*=( BigInt n )
 724 {
 725     operator=( operator*( n ) );
 726 }
 727
 728 BigInt BigInt::operator/( int n )
 729 {
 730     if( !n ) n /= n;        //XXX: force a crash
 731
 732     BigInt result( *this );
 733     result /= n;
 734     return result;
 735 }
 736
 737 BigInt BigInt::operator/( BigInt n )
 738 {
 739     if( !n ) n.size /= n.size;       //XXX: force a crash
 740
 741     BigInt result( *this );
 742     result /= n;
 743     return result;
 744 }
 745
 746 void BigInt::operator/=( int n )
 747 {
 748     divide( n );
 749 }
 750
 751 void BigInt::operator/=( BigInt n )
 752 {
 753     divide( n );
 754 }
 755
 756 int BigInt::operator%( int n )
 757 {
 758     BigInt tmp( *this );
 759     return tmp.divide( n );
 760 }
 761
 762 void BigInt::operator%=( int n )
 763 {
 764     operator=( divide( n ) );
 765 }
 766
 767 BigInt BigInt::operator%( BigInt n )
 768 {
 769     BigInt tmp( *this );
 770     return tmp.divide( n );
 771 }
 772
 773 void BigInt::operator%=( BigInt n )
 774 {
 775     operator=( divide( n ) );
 776 }
 777
 778 int BigInt::divide( int n )
 779 {
 780     if( !n ) n /= n;        //XXX: force a crash
 781
 782     int nsign = sig( n );
 783     n *= nsign;
 784     if( !sign ) return 0;
 785     sign *= nsign;
 786
 787     int tmp = 0;
 788     for( int i = size - 1; i >= 0; i-- )
 789     {
 790         tmp *= 10;
 791         tmp += digits[i];
 792         digits[i] = tmp / n;
 793         tmp -= digits[i] * n;
 794     }
 795     normalize();
 796     return tmp;
 797 }
 798
 799 BigInt BigInt::divide( BigInt n )
 800 {
 801     if( !n ) n.size /= n.size;         //XXX: force a crash
 802
 803     if( !sign ) return 0;
 804     sign *= n.sign;
 805
 806     int oldSign = n.sign;
 807     n.sign = 1;
 808
 809     BigInt tmp( 0, size );
 810     for( int i = size - 1; i >= 0; i-- )
 811     {
 812         tmp *= 10;
 813         tmp += digits[i];
 814         digits[i] = 0;
 815         while( tmp >= n ) { tmp -= n; digits[i]++; }
 816     }
 817     normalize();
 818
 819     n.sign = oldSign;
 820
 821     return tmp;
 822 }
 823
 824 // This is only exact to the first 15 or so digits, but it is
 825 // never an over-estimate
 826 BigInt BigInt::operator*( long double n )
 827 {
 828     // the number of digits after the decimal point to use
 829     int DIGS_AFTER_DOT = 15;
 830
 831     int nsign = sig( n );
 832     n *= nsign;
 833     int ndigs = n >= 1 ? ( int )log10( n ) + 1 : 0;
 834     BigInt result( 0, size + ndigs );
 835     result.sign = sign * nsign;
 836     if( !result.sign ) return result;
 837
 838     if( n >= 1 ) for( int i = 0; i < ndigs; i++ ) n /= 10;
 839     result.size = 0;
 840
 841     char afterDot[DIGS_AFTER_DOT + 1];
 842     memset( afterDot, 0, sizeof( afterDot ) );
 843
 844     // Keep going until the DIGS_AFTER_DOT'th digit after the decimal point
 845     for( int i = ndigs - 1; i >= -DIGS_AFTER_DOT; i-- )
 846     {
 847         n *= 10;
 848         int dig = ( int )floor( n );
 849         n -= dig;
 850         if( !dig ) continue;
 851
 852         int carry = 0;
 853         for( int j = 0; j < size || carry; j++ )
 854         {
 855             int newdig =
 856                 ( i + j < 0 ? afterDot[-( i + j )] : result.digits[i + j] )
 857                 + dig * digits[j]
 858                 + carry;
 859             ( i + j < 0 ? afterDot[-( i + j )] : result.digits[i + j] ) = newdig % 10;
 860             if( i + j >= 0 && result.digits[i + j] ) result.size >?= i + j + 1;
 861             carry = newdig / 10;
 862         }
 863     }
 864     if( !result.size ) result.sign = 0;
 865     return result;
 866 }
 867
 868 void BigInt::operator*=( long double n )
 869 {
 870     operator=( operator*( n ) );
 871 }
 872
 873 BigInt BigInt::operator<<( int n )
 874 {
 875     BigInt result( *this );
 876     result <<= n;
 877     return result;
 878 }
 879
 880 void BigInt::operator<<=( int n )
 881 {
 882     if( n < 0 ) operator>>=( -n );
 883     else if( n > 0 )
 884     {
 885         BigInt mult( 1, 4 * n );
 886         for( int i = ( 1 << 30 ); i; i >>= 1 )
 887         {
 888             mult *= mult;
 889             if( n & i ) mult *= 2;
 890         }
 891         operator*=( mult );
 892     }
 893 }
 894
 895 BigInt BigInt::operator>>( int n )
 896 {
 897     BigInt result( *this );
 898     result >>= n;
 899     return result;
 900 }
 901
 902 void BigInt::operator>>=( int n )
 903 {
 904     if( n < 0 ) operator<<=( -n );
 905     else if( n > 0 )
 906     {
 907         BigInt mult( 1, 4 * n );
 908         for( int i = ( 1 << 30 ); i; i >>= 1 )
 909         {
 910             mult *= mult;
 911             if( n & i ) mult *= 2;
 912         }
 913         operator/=( mult );
 914     }
 915 }
 916 /*
 917 BigInt BigInt::operator&( int n )
 918 {
 919 }
 920
 921 BigInt BigInt::operator&( BigInt n )
 922 {
 923 }
 924
 925 void BigInt::operator&=( int n )
 926 {
 927 }
 928
 929 void BigInt::operator&=( BigInt n )
 930 {
 931 }
 932
 933 BigInt BigInt::operator|( int n )
 934 {
 935 }
 936
 937 BigInt BigInt::operator|( BigInt n )
 938 {
 939 }
 940
 941 void BigInt::operator|=( int n )
 942 {
 943 }
 944
 945 void BigInt::operator|=( BigInt n )
 946 {
 947 }
 948
 949 BigInt BigInt::operator^( int n )
 950 {
 951 }
 952
 953 BigInt BigInt::operator^( BigInt n )
 954 {
 955 }
 956
 957 void BigInt::operator^=( int n )
 958 {
 959 }
 960
 961 void BigInt::operator^=( BigInt n )
 962 {
 963 }
 964
 965 BigInt BigInt::operator~()
 966 {
 967 }
 968 */
 969 BigInt BigInt::operator,( int n )
 970 {
 971     BigInt result( 0, size + ( int )sizeof( n ) * 8 );
 972     for( result.size = 0; n; result.size++ )
 973     {
 974         result.digits[result.size] = n % 10;
 975         n /= 10;
 976     }
 977     memcpy( result.digits + result.size, digits, size * sizeof( digits[0] ) );
 978     result.size += size;
 979     result.sign = 1;
 980     result.normalize();
 981     return result;
 982 }
 983
 984 BigInt BigInt::operator,( BigInt n )
 985 {
 986     BigInt result( 0, size + n.size );
 987     memcpy( result.digits, n.digits, n.size * sizeof( n.digits[0] ) );
 988     memcpy( result.digits + n.size, digits, size * sizeof( digits[0] ) );
 989     result.size = size + n.size;
 990     result.sign = 1;
 991     result.normalize();
 992     return result;
 993 }
 994
 995 bool BigInt::operator!()
 996 {
 997     return !size;
 998 }
 999
1000 BigInt::operator bool()
1001 {
1002     return size;
1003 }
1004
1005 //BigInt::operator int()
1006 //{
1007 //    return toInt();
1008 //}
1009
1010 BigInt::operator string()
1011 {
1012     return toString();
1013 }
1014
1015 bool BigInt::operator<( BigInt n )
1016 {
1017     return( compare( n ) < 0 );
1018 }
1019
1020 bool BigInt::operator>( BigInt n )
1021 {
1022     return( compare( n ) > 0 );
1023 }
1024
1025 bool BigInt::operator==( BigInt n )
1026 {
1027     return( compare( n ) == 0 );
1028 }
1029
1030 bool BigInt::operator<=( BigInt n )
1031 {
1032     return( compare( n ) <= 0 );
1033 }
1034
1035 bool BigInt::operator>=( BigInt n )
1036 {
1037     return( compare( n ) >= 0 );
1038 }
1039
1040 bool BigInt::operator<( int n )
1041 {
1042     return( compare( BigInt( n ) ) < 0 );
1043 }
1044
1045 bool BigInt::operator>( int n )
1046 {
1047     return( compare( BigInt( n ) ) > 0 );
1048 }
1049
1050 bool BigInt::operator==( int n )
1051 {
1052     return( compare( BigInt( n ) ) == 0 );
1053 }
1054
1055 bool BigInt::operator<=( int n )
1056 {
1057     return( compare( BigInt( n ) ) <= 0 );
1058 }
1059
1060 bool BigInt::operator>=( int n )
1061 {
1062     return( compare( BigInt( n ) ) >= 0 );
1063 }
1064
1065 int BigInt::compare( BigInt n )
1066 {
1067     if( sign < n.sign ) return -1;
1068     if( sign > n.sign ) return 1;
1069     if( size < n.size ) return -sign;
1070     if( size > n.size ) return sign;
1071     for( int i = size - 1; i >= 0; i-- )
1072     {
1073         if( digits[i] < n.digits[i] ) return -sign;
1074         else if( digits[i] > n.digits[i] ) return sign;
1075     }
1076     return 0;
1077 }
1078
1079 long double log2( BigInt x, long double epsilon = 0.000000000000001 )
1080 {
1081     static /* const */ long double O = 0.0;
1082     if( x.sign <= 0 ) return O / O;     // Return NaN
1083
1084     long double y = 0.0, z = 1.0, f = 0.0;
1085     while( x >= 2 )
1086     {
1087         if( x.divide( 2 ) ) f += 1.0;
1088         f /= 2.0;
1089         y++;
1090     }
1091     f += 1.0;
1092     while( z > epsilon )
1093     {
1094         f *= f;
1095         z /= 2.0;
1096         if( f >= 2.0 )
1097         {
1098             y += z;
1099             f /= 2.0;
1100         }
1101     }
1102     return y;
1103 }
1104
1105 inline long double log( BigInt x, long double epsilon = 0.000000000000001 )
1106 {
1107     return log2( x, epsilon ) * 0.6931471805599;
1108 }
1109
1110 inline long double log10( BigInt x, long double epsilon = 0.000000000000001 )
1111 {
1112     return log2( x, epsilon ) * 0.301029995664;
1113 }
1114
1115 inline long double lg( BigInt x, long double epsilon = 0.000000000000001 )
1116 {
1117     return log2( x, epsilon );
1118 }
1119
1120 inline long double ln( BigInt x, long double epsilon = 0.000000000000001 )
1121 {
1122     return log( x, epsilon );
1123 }
1124
1125
1126 int main()
1127 {
1128   int n;
1129   cin >> n;
1130   while (n--){
1131     string a, b;
1132     cin >> a >> b;
1133     BigInt x(a), y(b);
1134     cout << (x - y) << endl;
1135   }
1136   /*
1137     cout << "Constructors and copy constructors:" << endl;
1138     cout << "12345000 = " << BigInt( 12345000 ) << endl;
1139     BigInt b = BigInt( 12345000 );
1140     cout << "12345000 = " << b << endl;
1141     BigInt c; c = b;
1142     cout << "12345000 = " << c << endl;
1143     cout << "1234567890 = " << BigInt( ( long double )1234567890.49999 ) << endl;
1144     cout << endl;
1145
1146     cout << "Addition and subtraction:" << endl;
1147     cout << "123 + 234 = " << ( BigInt( 123 ) + 234 ).toInt() << endl;
1148     cout << "243 + 999 = " << ( BigInt( 243 ) + BigInt( 999 ) ) << endl;
1149     cout << "-123 + -321 = " << ( BigInt( -123 ) + BigInt( -321 ) ) << endl;
1150     cout << "-123 + 321 = " << ( BigInt( -123 ) + BigInt( 321 ) ) << endl;
1151     cout << "-2 + 5 = " << ( BigInt( -2 ) + 5 ) << endl;
1152     cout << "-2 + 5 = " << ( BigInt( -2 ) + BigInt( 5 ) ) << endl;
1153     cout << "-2 + -5 = " << ( BigInt( -2 ) + -5 ) << endl;
1154     cout << "-2 + -5 = " << ( BigInt( -2 ) + BigInt( -5 ) ) << endl;
1155     cout << "0 + -5 = " << ( BigInt( 0 ) + -5 ) << endl;
1156     cout << "0 + -5 = " << ( BigInt( 0 ) + BigInt( -5 ) ) << endl;
1157     cout << "4567 - 1234 = " << ( 4567 - BigInt( 1234 ) ) << endl;
1158     cout << "345 - 46 = " << ( BigInt( 345 ) - BigInt( 46 ) ) << endl;
1159     cout << "2 - 6 = " << ( BigInt( 2 ) - BigInt( 6 ) ) << endl;
1160     cout << "2 - 6 = " << ( BigInt( 2 ) - 6 ) << endl;
1161     cout << "0 - 5 = " << ( BigInt( 0 ) - 5 ) << endl;
1162     cout << "0 - 5 = " << ( BigInt( 0 ) - BigInt( 5 ) ) << endl;
1163     cout << "0 - -5 = " << ( BigInt( 0 ) - -5 ) << endl;
1164     cout << "0 - -5 = " << ( BigInt( 0 ) - BigInt( -5 ) ) << endl;
1165     cout << "10000 - 10000 = " << ( BigInt( 10000 ) - 10000 ) << endl;
1166     cout << "10000 - 10110 = " << ( BigInt( 10000 ) - 10110 ) << endl;
1167     cout << "4567 - 4568 = " << ( BigInt( 4567 ) - 4568 ) << endl;
1168     cout << "-4567 - -4568 = " << ( BigInt( -4567 ) - BigInt( -4568 ) ) << endl;
1169     cout << "999 - 9999 = " << ( BigInt( 999 ) - 9999 ) << endl;
1170     cout << "2000000000 + 2000000000 + 2000123456 = " << ( BigInt( 2000000000 ) + 2000000000 + BigInt( 2000123456 ) ) << endl;
1171     cout << "-34567 + 34568 = " << ( BigInt( -34567 ) + BigInt( 34568 ) ) << endl;
1172     cout << "10 - 1 = " << ( BigInt( 10 ) - 1 ) << endl;
1173     cout << "1 - 10 = " << ( BigInt( 1 ) - 10 ) << endl;
1174     cout << "Fib( 613 ) + Fib( 614 ) = " << (
1175         BigInt( "57535841731394367586444934959935162731893485882113791734636043664022186311322175066312007025864665068095897804714985049873571833" )
1176         +
1177         BigInt( "93094947492730684688120544687306111880728698574224279139760379700550384193434187688727692133714165658764281830930007773906603177" )
1178         ) << endl;
1179     cout << endl;
1180     cout << "Multiplication/division:" << endl;
1181     cout << "128 * 512 = " << ( BigInt( 128 ) * 512 ) << endl;
1182     cout << "0 * 12345 = " << ( BigInt( 0 ) * 12345 ) << endl;
1183     cout << "-123 * 0 = " << ( BigInt( -123 ) * 0 ) << endl;
1184     cout << "-12345 * 1000001 = " << ( BigInt( -12345 ) * BigInt( 1000001 ) ) << endl;
1185     cout << "-1 * -1 = " << ( BigInt( -1 ) * BigInt( -1 ) ) << endl;
1186     cout << "1024 / 2 = " << ( BigInt( 1024 ) / 2 ) << endl;
1187     cout << "-525474 / -789 = " << ( BigInt( -525474 ) / -789 ) << endl;
1188     cout << "-81 / 27 = " << ( BigInt( -81 ) / 27 ) << endl;
1189     cout << "0 / -888 = " << ( BigInt( 0 ) / -888 ) << endl;
1190     cout << "1024 / 2 = " << ( BigInt( 1024 ) / BigInt( 2 ) ) << endl;
1191     cout << "-525474 / -789 = " << ( BigInt( -525474 ) / BigInt( -789 ) ) << endl;
1192     cout << "-81 / 27 = " << ( BigInt( -81 ) / BigInt( 27 ) ) << endl;
1193     cout << "0 / -888 = " << ( BigInt( 0 ) / BigInt( -888 ) ) << endl;
1194     BigInt q = 1023;
1195     int rem = q.divide( 2 );
1196     cout << "1023 / 2 = " << q << " + " << rem << "/2" << endl;
1197     q = 1219255159;
1198     rem = q.divide( 98765 );
1199     cout << "1219255159 / 98765 = " << q << " + " << rem << "/98765" << endl;
1200     q = 121;
1201     rem = q.divide( 11 );
1202     cout << "121 / 11 = " << q << " + " << rem << "/11" << endl;
1203     q = 1023;
1204     BigInt rem2 = q.divide( BigInt( 2 ) );
1205     cout << "1023 / 2 = " << q << " + " << rem2 << "/2" << endl;
1206     q = 1219255159;
1207     rem2 = q.divide( BigInt( 98765 ) );
1208     cout << "1219255159 / 98765 = " << q << " + " << rem2 << "/98765" << endl;
1209     q = 121;
1210     rem2 = q.divide( BigInt( 11 ) );
1211     cout << "121 / 11 = " << q << " + " << rem2 << "/11" << endl;
1212     q = 9999;
1213     rem2 = q.divide( BigInt( 9 ) );
1214     cout << "9999 / 9 = " << q << " + " << rem2 << "/9" << endl;
1215     cout << "1024 * 15.37 = " << BigInt( 1024 ) * 15.37l << endl;
1216     cout << "100 * 0.5 = " << BigInt( 100 ) * 0.5l << endl;
1217     cout << "123456789 * 0.123456789 = " << BigInt( 123456789 ) * 0.123456789l << endl;
1218     cout << "4286 * -0.5 = " << BigInt( 4286 ) * -0.5l << endl;
1219     cout << "29384723 * 1.0 = " << BigInt( 29384723 ) * 1.0l << endl;
1220     cout << "29384723 * -1.0 = " << BigInt( 29384723 ) * -1.0l << endl;
1221     cout << "3874928345 * 0.0 = " << BigInt( "3874928345" ) * 0.0l << endl;
1222     BigInt n = 1000;
1223     cout << "n = 1000: n*n*(8+n*(12+n*(3+n*n))) = " << n*n*(8+n*(12+n*(3+n*n))) << endl;
1224
1225     cout << endl;
1226     cout << "Concatenation:" << endl;
1227     cout << "123,456 = " << ( BigInt( 123 ), 456 ) << endl;
1228     cout << "9999,55 = " << ( BigInt( 9999 ), BigInt( 55 ) ) << endl;
1229     cout << "0,1 = " << ( BigInt( 0 ), BigInt( 1 ) ) << endl;
1230     cout << "0,0 = " << ( BigInt( 0 ), 0 ) << endl;
1231     cout << "0,0 = " << ( BigInt( 0 ), BigInt( 0 ) ) << endl;
1232     cout << endl;
1233     cout << "Reflection:" << endl;
1234     BigInt x = 11;
1235     cout << "11 + 11 = " << ( x + x ) << endl;
1236     cout << "11 * 11 = " << ( x * x ) << endl;
1237     x += x;
1238     cout << "11 + 11 = " << x << endl;
1239     x *= x;
1240     cout << "22 * 22 = " << x << endl;
1241     cout << endl;
1242     cout << "Bitwise operations:" << endl;
1243     cout << "1 << 10 = " << ( 1 << 10 ) << " = " << ( BigInt( 1 ) << 10 ) << endl;
1244     cout << "-7 << 2 = " << ( -7 << 2 ) << " = " << ( BigInt( -7 ) << 2 ) << endl;
1245     cout << "3 << 8 = " << ( 3 << 8 ) << " = " << ( BigInt( 3 ) << 8 ) << endl;
1246     cout << "3 << 9 = " << ( 3 << 9 ) << " = " << ( BigInt( 3 ) << 9 ) << endl;
1247     cout << "1024 >> 9 = " << ( 1024 >> 9 ) << " = " << ( BigInt( 1024 ) >> 9 ) << endl;
1248     cout << "-1 >> 4 = " << (-1 >> 4) << " = " << ( BigInt( -1 ) >> 4 ) << endl;
1249     cout << endl;
1250     cout << "Input:" << endl;
1251     istringstream in( "1234567890" );
1252     in >> x;
1253     cout << "1234567890 = " << x << endl;
1254     istringstream in2( " \t\n\r01234 -00009876\t" );
1255     in2 >> x >> rem2;
1256     cout << "1234 = " << x << endl;
1257     cout << "-9876 = " << rem2 << endl;
1258     cout << endl;
1259     cout << "Exhaustion:" << endl;
1260     BigInt *table = new BigInt[10240];
1261     table[0] = 0; table[1] = 1;
1262     for( int i = 2; i < 10240; i++ )
1263         table[i] = table[i - 1] + table[i - 2];
1264     cout << "Fibonacci( 615 )  = " << table[615] << endl;
1265     cout << "Fibonacci( 10000 )  = " << table[10000] << endl;
1266     delete [] table;
1267     cout << endl;
1268     cout << "Logarithms" << endl;
1269     cout << "log2( 1024 ) = " << log2( BigInt( 1024 ) ) << endl;
1270     cout << "log2( 6 ) = " << log2( BigInt( 6 ) ) << endl;
1271     cout << "log( 0 ) = " << log( BigInt( 0 ) ) << endl;
1272     cout << "log10( 1000000 ) = " << log10( BigInt( 10000000 ) ) << endl;
1273     cout << "log( 1234567 ) = " << log( BigInt( 1234567 ) ) << endl;
1274   */
1275     return 0;
1276 }
1277